package list;

/**
 * 合 并两个链表，使它有效
 * step 1：判断空链表的情况，只要有一个链表为空，那答案必定就是另一个链表了，就算另一个链表也为空。
 * step 2：新建一个空的表头后面连接两个链表排序后的节点，两个指针分别指向两链表头。
 * step 3：遍历两个链表都不为空的情况，取较小值添加在新的链表后面，每次只把被添加的链表的指针后移。
 * step 4：遍历到最后肯定有一个链表还有剩余的节点，它们的值将大于前面所有的，直接连在新的链表后面即可。
 * @Author wy
 * @Description TODO
 * @Date 2023/6/8 14:06
 * @Version 1.0
 */
public class List02 {


    public static ListNode Merge(ListNode list1,ListNode list2) {
        //step 1：判断空链表的情况，只要有一个链表为空，那答案必定就是另一个链表了，就算另一个链表也为空。
        //一个已经为空了，直接返回另一个
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }

        //step 2：新建一个空的表头后面连接两个链表排序后的节点，两个指针分别指向两链表头。
        //加一个表头
        ListNode head = new ListNode(0);

        //当前指针
        ListNode cur = head;

        //两个链表都要不为空
        while(list1 != null && list2 != null){
            //取较小值的节点
            if(list1.val <= list2.val){
                cur.next = list1;
                //只移动取值的指针
                list1 = list1.next;
            }else{
                cur.next = list2;
                //只移动取值的指针
                list2 = list2.next;
            }
            //指针后移
            cur = cur.next;
        }

        //先判断 list1!=null
        if(list1!=null){
            cur.next = list1;
        }else{
            cur.next=list2;
        }

        return  head.next;
    }


    public static void main(String[] args) {
       ListNode first=oneListNode();
       ListNode second=twoListNode();


       PrintNodeUtil.show(first);
       PrintNodeUtil.show(second);

        System.out.println("合并");
        ListNode newList=Merge(first,second);

        PrintNodeUtil.show(newList);


    }

    public static ListNode oneListNode(){
        ListNode header=new ListNode(1,new ListNode(3,new ListNode(5,new ListNode(10,new ListNode(18)))));
        return header;
    }

    public static ListNode twoListNode(){
        ListNode header=new ListNode(2,new ListNode(3,new ListNode(7,new ListNode(8,new ListNode(9)))));
        return header;
    }

}
